#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=15029918
#Google interview question
"""
Given two string S1 and S2. S1 contains from A-Z and S2 contains A-Z, * and ?
Where * means any character 0 or any number of times
Where ? means any character 0 or 1 number of times
Write a program to determine whether S2 matches S1
"""
import os, re, sys, getopt
import logging
import locale


def is_match_lobatt(s, pattern):
    print "s=" + s + "\tpattern="+pattern
    if len(s) == 0:
        if pattern == '*' or pattern == '?': return True
        return False
    if len(pattern) == 0 or pattern == '*': return True
    i, j = 0, 0
    while i < len(s) and j < len(pattern):
        if pattern[j] == '*':
            last = 0
            k = i
            j += 1
            if j >= len(pattern): return True
            while k < len(s):
                if(s[k] == pattern[j]):
                    i = k
                k += 1
        elif pattern[j] == '?':
            if j + 1 < len(pattern):
                if s[i] != pattern[j + 1]: i += 1
            j += 1
        elif pattern[j] == s[i]:
            j += 1
            i += 1
        else:
            return False
    if i == len(s) and j == len(pattern): return True
    return False
    
def is_match_lobatt_2(s, pattern):
    print "s=" + s + "\tpattern="+pattern
    return is_match_lobatt_recur(s, pattern)

def is_match_lobatt_recur(s, pattern):
    #print "s=" + s + "\tpattern="+pattern
    if len(s) == 0:
        if len(pattern) ==0 or pattern == '*' or pattern == '?': return True
        return False
    if len(pattern) == 0 or pattern == '*': return True
    i, j = 0, 0
    if s[i] == pattern[j]: return is_match_lobatt_recur(s[1:],pattern[1:])
    elif pattern[j] == '?':
        return is_match_lobatt_recur(s[1:],pattern[1:]) or is_match_lobatt_recur(s,pattern[1:])
    elif pattern[j] == '*':
        if j + 1 >= len(pattern): return True
        for i in rang(0, len(s)):
            if is_match_lobatt_recur(s[i:],pattern[j + 1:]): return True
        return is_match_lobatt_recur(s,pattern[j + 1:])
    else: return False
    
    
def is_match_david_1(string, pattern, string_index, pattern_index):
    if string_index == len(string) and pattern_index == len(pattern): return True
    if pattern_index == len(pattern): return False
    if pattern[pattern_index] == '?':
        return is_match_david_1(string, pattern, string_index, pattern_index + 1) or is_match_david_1(string, pattern, string_index + 1, pattern_index + 1)
    if pattern[pattern_index] == '*':
        pre_char = -1
        for i in range(string_index, len(string) + 1):
            if is_match_david_1(string, pattern, i, pattern_index + 1): return True
            if i == len(string) or pre_char != -1 and pre_char != string[i]: break
            pre_char = string[i]
    if string_index == len(string): return False
    if string[string_index] == pattern[pattern_index]: return is_match_david_1(string, pattern, string_index + 1, pattern_index + 1)
    return False

def is_match_david(string, pattern):
    print "s=" + string + "\tpattern="+pattern
    return is_match_david_1(string, pattern, 0, 0)

if __name__ == '__main__':
    try:
        opts, args = getopt.getopt(sys.argv[1:], 'd:', ['date=', 'debug'])
        for opt, arg in opts:
            if opt in ['-d', '--date']: date = datetime.date(int(arg[:4]), int(arg[4:6]), int(arg[6:8]))
            elif opt in ['--debug']:
                debug = True
    except getopt.GetoptError, err:
        print str(err)
        print __doc__
        sys.exit(1)
        
    string = "abcsdedsds"
    pattern = "ab?sde*ds"
    print is_match_david(string, pattern)
